package com.lry.basic.algorithm.common;
import java.util.ArrayList;
import java.util.List;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/9/16
 */
//        给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
//        例如，给定三角形：
//        [
//           [2],
//          [3,4],
//         [6,5,7],
//        [4,1,8,3]
//        ]
//        自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）
public class TriangleMinTotal{
    public static void main(String[] args) {
        TriangleMinTotal t = new TriangleMinTotal();
        List<List<Integer>> res = new ArrayList<>();
        List<Integer>l1 = new ArrayList<>();
        l1.add(2);
        res.add(l1);
        List<Integer>l2 = new ArrayList<>();
        l2.add(3);
        l2.add(4);
        res.add(l2);
        List<Integer>l3 = new ArrayList<>();
        l3.add(6);
        l3.add(5);
        l3.add(7);
        res.add(l3);
        List<Integer>l4 = new ArrayList<>();
        l4.add(4);
        l4.add(1);
        l4.add(8);
        l4.add(3);
        res.add(l4);
        minTotal(0,res.get(0).get(0),0,res);
        System.out.println(min);

        System.out.println(t.minimumTotal(res));

        System.out.println(t.minimumTotal2(res));
    }
    static int min = Integer.MAX_VALUE;
    //i是第几层，j是每一层某个元素的下标 时间太长
    private static void minTotal(int i,int sum,int j,List<List<Integer>> triangle){
        if(i==triangle.size()-1&&sum<min){
            min = sum;
        }
        if(i<triangle.size()-1){
            minTotal(i+1,sum+triangle.get(i+1).get(j),j,triangle);
            minTotal(i+1,sum+triangle.get(i+1).get(j+1),j+1,triangle);
        }
    }

    int row;
    Integer[][]memo;
    public int minimumTotal(List<List<Integer>> triangle) {
        row = triangle.size();
        memo = new Integer[row][row];
        return helper(0,0, triangle);
    }

    /**
     * 自顶向下记忆化搜索
     * @param level 当前层次
     * @param index 当前层次下标
     * @param triangle 三角形
     * @return
     */
    private int helper(int level, int index, List<List<Integer>> triangle) {
        //记忆化搜索直接返回
        if(memo[level][index]!=null){
            return memo[level][index];
        }
        //最后一层直接返回
        if(level==row-1){
            return memo[level][index]=triangle.get(level).get(index);
        }
        //不是最后一层的话，去找下一层，并返回当前层元素+下一层较小的元素
        int left = helper(level+1,index,triangle);
        int right = helper(level+1,index+1,triangle);
        return memo[level][index]=triangle.get(level).get(index)+Math.min(left,right);
    }

    /**
     * 自底向上遍历
     * @param triangle
     * @return
     */
    public int minimumTotal2(List<List<Integer>> triangle) {
        int level = triangle.size()-1;//定位到最底层
        while(level>0){//没有走到顶层 就一直循环
            for(int i=0;i<level;i++){//遍历该层所有元素
                //该层两两比较较小的出来
                int min = Math.min(triangle.get(level).get(i),triangle.get(level).get(i+1));
                //上一层的值
                int r = triangle.get(level-1).get(i);
                //更新上一层的值
                triangle.get(level-1).set(i,r+min);
            }
            level--;
        }
        //返回顶层元素
        return triangle.get(0).get(0);
    }
}
